第一部分选择题
一、单项选择题:本大题共15小题,每小题1分，共15分。在每小题列出的备选项中只有一项
r V%rP(x)r V/P(X)O8.下列度数序列中，不能构成简单无向图的是
U,2,2,3}11,2,2,2,1}一个6阶无向简单图，其结点的最大度数为A.5
B.6
C.7
D.8
10.集合A上的对称关系R的关系矩阵为则
B.M的对角线上元素全是1
M的对角线上元素全是0是最符合题目要求的，请将其选出。
1.令p：今天下雨,q：我今天进城。命题“因为今天不下雨，所以我今天进城”的符号化形式为
C.M为对称矩阵
M为反对称矩阵11.已知A、8、C、D是任意集合,则下列各式不成立的是
则命题“对每个实数，都存在一个比它更大的实数”
(4-B)xC=”xC)-(BxC)对应的谓词公式是
(A©B)x(C©Z))= (AxC)@(BxD)(4©B) xC= (AxC) ©(BxC)(AUfi)xC=(AxC) U(BxC)Vx(R(x)->3y(^(x,y) A/?(y)))V%(R(x)一AR(%)))12.要从完全图&中得到一颗生成树，需要删除的边数为
3x(7?(x)^-Vy(^(x,y) A/?(y)))3.下列关于小项和大项的性质，不正确的是
\/x(R(x)A 3yQ(x,y)A.任意两个不同小项的合取必为假
B.任意两个不同大项的析取必为真
C.任意两个不同小项的合取必为真
D.大项的否定是小项
4-下列是欧拉图的为
集合4={1,2,3}上的关系/?=|,,,,}，则夫不晕A.自反关系 B.对称关系 C.传递关系 D.反对称关系
简单无向图C有10条边,每个结点都是2度结点，则C的结点数为A.5 B.10 C. 15 D.20
13.设C为9阶无向简单图，下列命题中可成立的是
A.G的每个结点的度数均为3
B.G的每个结点的度数均为6
C.C的每个结点的度数均为5
D.C的每个结点的度数均为7
14.下列4个偏序集的图形，不能构成格的是
15.设集合4的元素个数为4,则4上所有的等价关系的个数为
A.4
B.8
1015第二部分非选择题
二、填空题:本大题共10小题,每小题2分，共20分。
设4=|1,2}，则疽= o设集合 A= {1,2,3,4},且 A 上的关系 R】={ ,,} ,R2= \ ,, |，则 dom(R[ U/?2) = ,ran(&】 U^2)= 。集合 A = |1,2,3,4} ,4 上的关系 R = ],,,0)的真值为 ，命题公式Vx 3y(x22)个命题变项的命题公式4的主析取范式包括k个小项，则4的主合取范式必 定包括 个大项。三、计算题:本大题共5小题,每小题6分，共30分。
用真位表法判定下列逻辑等价式成立(P—Q) A (R—Q) —P V R—Q
用等值演算法求命题公式(P-r Q)_>R的主析取范式。对于实数集合R,下表所列的二元运算是否具有左边一列中的那些性质，填写下表(具备某 项性质填写“是”，不具备填写“否”，请将题28表画在答题卡上作答)对于任意集合4和B,证明:P(.4)nP(8) = P(4CB) 其中P(Q表示集合A的赛集。
证明：Vx(P(x)—>Vy(Q(y)^-i(x,y)) ) Vx Vy( (P(x) AQ(y))—»L(x,y))设儿阶图C中有m条边,其中A( C)为图C的最大度,5( C)为图G的最小度，证明:8( G) W2zn//i W A( G)
五、综合应用题:本大题共2小题,每小题7分，共14分。
分析一个n阶无向图G的邻接矩阵Me,如果该图为树，则：邻接矩阵Me中值为1的元素个数为多少？MG+Ml+Ml+-+Ml中值为0的元素个数为多少？设集合A= \a,b,c\ ,写出4的驀集P(4)；画出偏序关系{P(A)的哈斯图，并指出该偏序关系的极大元和极小元。题28表
运算 性质’\^ x-yx・y可结合性 可交换性 一颗树有n2个结点度数为2,几3个结点度数为3,-,nk个结点度数为奴求其度数为1的 结点数的的值。